/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
class FannkucRedux {

    public static long timeInUs() {
        return System.nanoTime();
    }
    // Modify n value to change the difficulty of the benchmark

    public static int input = 8;

    public static int fannkuch(int n) {
        int[] perm = new int[n];
        int[] count = new int[n];
        int[] perm1 = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = 0;
            count[i] = 0;
            perm1[i] = 0;
        }
        for (int j = 0; j < (n - 1); j++) {
            perm1[j] = j;
        }

        int f = 0;
        int i = 0;
        int k = 0;
        int r = n;
        int flips = 0;
        int nperm = 0;
        int checksum = 0;

        while (r > 0) {
            i = 0;
            while (r != 1) {
                count[r - 1] = r;
                r -= 1;
            }
            while (i < n) {
                perm[i] = perm1[i];
                i += 1;
            }

   			// Count flips and update max and checksum
            f = 0;
            k = perm[0];
            while (k != 0) {
                i = 0;
                while (2 * i < k) {
                    int t = perm[i];
                    perm[i] = perm[k - i];
                    perm[k - i] = t;
                    i += 1;
                }
                k = perm[0];
                f += 1;
            }
            if (f > flips) {
                flips = f;
            }
            if ((nperm & 0x1) == 0) {
                checksum += f;
            } else {
                checksum -= f;
            }

			// Use incremental change to generate another permutation
            boolean go = true;
            while (go) {
                if (r == n) {
                    return flips;
                }
                int p0 = perm1[0];
                i = 0;
                while (i < r) {
                    int j = i + 1;
                    perm1[i] = perm1[j];
                    i = j;
                }
                perm1[r] = p0;

                count[r] -= 1;
                if (count[r] > 0) {
                    go = false;
                } else {
                    r += 1;
                }
            }
            nperm += 1;
        }
        return flips;
    }

}
/*
 * @State
 * @Tags Jetstream2
 */
class Benchmark {
    public static void main(String[] args) {
        runFannkucRedux();
    }
    /*
     *@Benchmark
     */
    public static void runFannkucRedux(){
        int n = FannkucRedux.input;
        int res = 0;
        long start = FannkucRedux.timeInUs();
        res = FannkucRedux.fannkuch(n);
        long end = FannkucRedux.timeInUs();

        long time = (end - start);
        System.out.println("res: " + res);
        System.out.println("Array Access - RunFannkucRedux:" + time / 1_000_000.0 + "ms");
    }

}